"""
76. 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
"""
import sys
from collections import Counter


class Solution:

    def minWindow(self, s: str, t: str) -> str:
        left = 0
        right = 0
        start = 0
        length = sys.maxsize
        need = Counter(t)
        window = Counter()
        valid = 0

        while right < len(s):
            # 扩大窗口
            c = s[right]
            right += 1
            if c in need:
                window[c] += 1
                if need[c] == window[c]:
                    valid += 1

            while valid == len(need):
                # 更新结果
                if right - left < length:
                    length = right - left
                    start = left
                # 减小窗口
                c = s[left]
                left += 1
                if c in need:
                    if need[c] == window[c]:
                        valid -= 1
                    window[c] -= 1

        return '' if length == sys.maxsize else s[start:start+length]


if __name__ == '__main__':
    w = Counter()
    w['c'] += 1
    print(Counter())
    print(Counter('abcdef'))
    print(w['a'])